/***************************************************************************/
/*                                                                         */
/*  ftoutln.c                                                              */
/*                                                                         */
/*    FreeType outline management (body).                                  */
/*                                                                         */
/*  Copyright 1996-2008, 2010, 2012 by                                     */
/*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
/*                                                                         */
/*  This file is part of the FreeType project, and may only be used,       */
/*  modified, and distributed under the terms of the FreeType project      */
/*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
/*  this file you indicate that you have read the license and              */
/*  understand and accept it fully.                                        */
/*                                                                         */
/***************************************************************************/


/*************************************************************************/
/*                                                                       */
/* All functions are declared in freetype.h.                             */
/*                                                                       */
/*************************************************************************/


#include <ft2build.h>
#include FT_OUTLINE_H
#include FT_INTERNAL_OBJECTS_H
#include FT_INTERNAL_DEBUG_H
#include FT_TRIGONOMETRY_H


/*************************************************************************/
/*                                                                       */
/* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
/* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
/* messages during execution.                                            */
/*                                                                       */
#undef  FT_COMPONENT
#define FT_COMPONENT  trace_outline


static
const FT_Outline null_outline = { 0, 0, 0, 0, 0, 0 };


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( FT_Error )
FT_Outline_Decompose( FT_Outline *outline,
                      const FT_Outline_Funcs *func_interface,
                      void *user )
{
#undef SCALED
#define SCALED( x )  ( ( (x) << shift ) - delta )

    FT_Vector v_last;
    FT_Vector v_control;
    FT_Vector v_start;

    FT_Vector *point;
    FT_Vector *limit;
    char *tags;

    FT_Error error;

    FT_Int n;         /* index of contour in outline     */
    FT_UInt first;     /* index of first point in contour */
    FT_Int tag;       /* current point's state           */

    FT_Int shift;
    FT_Pos delta;


    if ( !outline || !func_interface )
    {
        return FT_Err_Invalid_Argument;
    }

    shift = func_interface->shift;
    delta = func_interface->delta;
    first = 0;

    for ( n = 0; n < outline->n_contours; n++ )
    {
        FT_Int last;  /* index of last point in contour */


        FT_TRACE5(( "FT_Outline_Decompose: Outline %d\n", n ));

        last = outline->contours[ n ];
        if ( last < 0 )
        {
            goto Invalid_Outline;
        }
        limit = outline->points + last;

        v_start = outline->points[ first ];
        v_start.x = SCALED( v_start.x );
        v_start.y = SCALED( v_start.y );

        v_last = outline->points[ last ];
        v_last.x = SCALED( v_last.x );
        v_last.y = SCALED( v_last.y );

        v_control = v_start;

        point = outline->points + first;
        tags = outline->tags + first;
        tag = FT_CURVE_TAG( tags[ 0 ] );

        /* A contour cannot start with a cubic control point! */
        if ( tag == FT_CURVE_TAG_CUBIC )
        {
            goto Invalid_Outline;
        }

        /* check first point to determine origin */
        if ( tag == FT_CURVE_TAG_CONIC )
        {
            /* first point is conic control.  Yes, this happens. */
            if ( FT_CURVE_TAG( outline->tags[ last ] ) == FT_CURVE_TAG_ON )
            {
                /* start at last point if it is on the curve */
                v_start = v_last;
                limit--;
            }
            else
            {
                /* if both first and last points are conic,         */
                /* start at their middle and record its position    */
                /* for closure                                      */
                v_start.x = ( v_start.x + v_last.x ) / 2;
                v_start.y = ( v_start.y + v_last.y ) / 2;

                v_last = v_start;
            }
            point--;
            tags--;
        }

        FT_TRACE5(( "  move to (%.2f, %.2f)\n",
                v_start.x / 64.0, v_start.y / 64.0 ));
        error = func_interface->move_to( &v_start, user );
        if ( error )
        {
            goto Exit;
        }

        while ( point < limit )
        {
            point++;
            tags++;

            tag = FT_CURVE_TAG( tags[ 0 ] );
            switch ( tag )
            {
                case FT_CURVE_TAG_ON:  /* emit a single line_to */
                {
                    FT_Vector vec;


                    vec.x = SCALED( point->x );
                    vec.y = SCALED( point->y );

                    FT_TRACE5(( "  line to (%.2f, %.2f)\n",
                            vec.x / 64.0, vec.y / 64.0 ));
                    error = func_interface->line_to( &vec, user );
                    if ( error )
                    {
                        goto Exit;
                    }
                    continue;
                }

                case FT_CURVE_TAG_CONIC:  /* consume conic arcs */
                    v_control.x = SCALED( point->x );
                    v_control.y = SCALED( point->y );

                Do_Conic:
                    if ( point < limit )
                    {
                        FT_Vector vec;
                        FT_Vector v_middle;


                        point++;
                        tags++;
                        tag = FT_CURVE_TAG( tags[ 0 ] );

                        vec.x = SCALED( point->x );
                        vec.y = SCALED( point->y );

                        if ( tag == FT_CURVE_TAG_ON )
                        {
                            FT_TRACE5(( "  conic to (%.2f, %.2f)"
                                        " with control (%.2f, %.2f)\n",
                                    vec.x / 64.0, vec.y / 64.0,
                                    v_control.x / 64.0, v_control.y / 64.0 ));
                            error = func_interface->conic_to( &v_control, &vec, user );
                            if ( error )
                            {
                                goto Exit;
                            }
                            continue;
                        }

                        if ( tag != FT_CURVE_TAG_CONIC )
                        {
                            goto Invalid_Outline;
                        }

                        v_middle.x = ( v_control.x + vec.x ) / 2;
                        v_middle.y = ( v_control.y + vec.y ) / 2;

                        FT_TRACE5(( "  conic to (%.2f, %.2f)"
                                    " with control (%.2f, %.2f)\n",
                                v_middle.x / 64.0, v_middle.y / 64.0,
                                v_control.x / 64.0, v_control.y / 64.0 ));
                        error = func_interface->conic_to( &v_control, &v_middle, user );
                        if ( error )
                        {
                            goto Exit;
                        }

                        v_control = vec;
                        goto Do_Conic;
                    }

                    FT_TRACE5(( "  conic to (%.2f, %.2f)"
                                " with control (%.2f, %.2f)\n",
                            v_start.x / 64.0, v_start.y / 64.0,
                            v_control.x / 64.0, v_control.y / 64.0 ));
                    error = func_interface->conic_to( &v_control, &v_start, user );
                    goto Close;

                default:  /* FT_CURVE_TAG_CUBIC */
                {
                    FT_Vector vec1, vec2;


                    if ( point + 1 > limit ||
                         FT_CURVE_TAG( tags[ 1 ] ) != FT_CURVE_TAG_CUBIC )
                    {
                        goto Invalid_Outline;
                    }

                    point += 2;
                    tags += 2;

                    vec1.x = SCALED( point[ -2 ].x );
                    vec1.y = SCALED( point[ -2 ].y );

                    vec2.x = SCALED( point[ -1 ].x );
                    vec2.y = SCALED( point[ -1 ].y );

                    if ( point <= limit )
                    {
                        FT_Vector vec;


                        vec.x = SCALED( point->x );
                        vec.y = SCALED( point->y );

                        FT_TRACE5(( "  cubic to (%.2f, %.2f)"
                                    " with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
                                vec.x / 64.0, vec.y / 64.0,
                                vec1.x / 64.0, vec1.y / 64.0,
                                vec2.x / 64.0, vec2.y / 64.0 ));
                        error = func_interface->cubic_to( &vec1, &vec2, &vec, user );
                        if ( error )
                        {
                            goto Exit;
                        }
                        continue;
                    }

                    FT_TRACE5(( "  cubic to (%.2f, %.2f)"
                                " with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
                            v_start.x / 64.0, v_start.y / 64.0,
                            vec1.x / 64.0, vec1.y / 64.0,
                            vec2.x / 64.0, vec2.y / 64.0 ));
                    error = func_interface->cubic_to( &vec1, &vec2, &v_start, user );
                    goto Close;
                }
            }
        }

        /* close the contour with a line segment */
        FT_TRACE5(( "  line to (%.2f, %.2f)\n",
                v_start.x / 64.0, v_start.y / 64.0 ));
        error = func_interface->line_to( &v_start, user );

        Close:
        if ( error )
        {
            goto Exit;
        }

        first = last + 1;
    }

    FT_TRACE5(( "FT_Outline_Decompose: Done\n", n ));
    return FT_Err_Ok;

    Exit:
    FT_TRACE5(( "FT_Outline_Decompose: Error %d\n", error ));
    return error;

    Invalid_Outline:
    return FT_Err_Invalid_Outline;
}


FT_EXPORT_DEF( FT_Error )
FT_Outline_New_Internal( FT_Memory memory,
                         FT_UInt numPoints,
                         FT_Int numContours,
                         FT_Outline *anoutline )
{
    FT_Error error;


    if ( !anoutline || !memory )
    {
        return FT_Err_Invalid_Argument;
    }

    *anoutline = null_outline;

    if ( FT_NEW_ARRAY( anoutline->points, numPoints ) ||
         FT_NEW_ARRAY( anoutline->tags, numPoints ) ||
         FT_NEW_ARRAY( anoutline->contours, numContours ))
    {
        goto Fail;
    }

    anoutline->n_points = ( FT_UShort ) numPoints;
    anoutline->n_contours = ( FT_Short ) numContours;
    anoutline->flags |= FT_OUTLINE_OWNER;

    return FT_Err_Ok;

    Fail:
    anoutline->flags |= FT_OUTLINE_OWNER;
    FT_Outline_Done_Internal( memory, anoutline );

    return error;
}


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( FT_Error )
FT_Outline_New( FT_Library library,
                FT_UInt numPoints,
                FT_Int numContours,
                FT_Outline *anoutline )
{
    if ( !library )
    {
        return FT_Err_Invalid_Library_Handle;
    }

    return FT_Outline_New_Internal( library->memory, numPoints,
                                    numContours, anoutline );
}


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( FT_Error )
FT_Outline_Check( FT_Outline *outline )
{
    if ( outline )
    {
        FT_Int n_points = outline->n_points;
        FT_Int n_contours = outline->n_contours;
        FT_Int end0, end;
        FT_Int n;


        /* empty glyph? */
        if ( n_points == 0 && n_contours == 0 )
        {
            return 0;
        }

        /* check point and contour counts */
        if ( n_points <= 0 || n_contours <= 0 )
        {
            goto Bad;
        }

        end0 = end = -1;
        for ( n = 0; n < n_contours; n++ )
        {
            end = outline->contours[ n ];

            /* note that we don't accept empty contours */
            if ( end <= end0 || end >= n_points )
            {
                goto Bad;
            }

            end0 = end;
        }

        if ( end != n_points - 1 )
        {
            goto Bad;
        }

        /* XXX: check the tags array */
        return 0;
    }

    Bad:
    return FT_Err_Invalid_Argument;
}


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( FT_Error )
FT_Outline_Copy( const FT_Outline *source,
                 FT_Outline *target )
{
    FT_Int is_owner;


    if ( !source || !target ||
         source->n_points != target->n_points ||
         source->n_contours != target->n_contours )
    {
        return FT_Err_Invalid_Argument;
    }

    if ( source == target )
    {
        return FT_Err_Ok;
    }

    FT_ARRAY_COPY( target->points, source->points, source->n_points );

    FT_ARRAY_COPY( target->tags, source->tags, source->n_points );

    FT_ARRAY_COPY( target->contours, source->contours, source->n_contours );

    /* copy all flags, except the `FT_OUTLINE_OWNER' one */
    is_owner = target->flags & FT_OUTLINE_OWNER;
    target->flags = source->flags;

    target->flags &= ~FT_OUTLINE_OWNER;
    target->flags |= is_owner;

    return FT_Err_Ok;
}


FT_EXPORT_DEF( FT_Error )
FT_Outline_Done_Internal( FT_Memory memory,
                          FT_Outline *outline )
{
    if ( memory && outline )
    {
        if ( outline->flags & FT_OUTLINE_OWNER )
        {
            FT_FREE( outline->points );
            FT_FREE( outline->tags );
            FT_FREE( outline->contours );
        }
        *outline = null_outline;

        return FT_Err_Ok;
    }
    else
    {
        return FT_Err_Invalid_Argument;
    }
}


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( FT_Error )
FT_Outline_Done( FT_Library library,
                 FT_Outline *outline )
{
    /* check for valid `outline' in FT_Outline_Done_Internal() */

    if ( !library )
    {
        return FT_Err_Invalid_Library_Handle;
    }

    return FT_Outline_Done_Internal( library->memory, outline );
}


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( void )
FT_Outline_Get_CBox( const FT_Outline *outline,
                     FT_BBox *acbox )
{
    FT_Pos xMin, yMin, xMax, yMax;


    if ( outline && acbox )
    {
        if ( outline->n_points == 0 )
        {
            xMin = 0;
            yMin = 0;
            xMax = 0;
            yMax = 0;
        }
        else
        {
            FT_Vector *vec = outline->points;
            FT_Vector *limit = vec + outline->n_points;


            xMin = xMax = vec->x;
            yMin = yMax = vec->y;
            vec++;

            for ( ; vec < limit; vec++ )
            {
                FT_Pos x, y;


                x = vec->x;
                if ( x < xMin )
                { xMin = x; }
                if ( x > xMax )
                { xMax = x; }

                y = vec->y;
                if ( y < yMin )
                { yMin = y; }
                if ( y > yMax )
                { yMax = y; }
            }
        }
        acbox->xMin = xMin;
        acbox->xMax = xMax;
        acbox->yMin = yMin;
        acbox->yMax = yMax;
    }
}


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( void )
FT_Outline_Translate( const FT_Outline *outline,
                      FT_Pos xOffset,
                      FT_Pos yOffset )
{
    FT_UShort n;
    FT_Vector *vec;


    if ( !outline )
    {
        return;
    }

    vec = outline->points;

    for ( n = 0; n < outline->n_points; n++ )
    {
        vec->x += xOffset;
        vec->y += yOffset;
        vec++;
    }
}


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( void )
FT_Outline_Reverse( FT_Outline *outline )
{
    FT_UShort n;
    FT_Int first, last;


    if ( !outline )
    {
        return;
    }

    first = 0;

    for ( n = 0; n < outline->n_contours; n++ )
    {
        last = outline->contours[ n ];

        /* reverse point table */
        {
            FT_Vector *p = outline->points + first;
            FT_Vector *q = outline->points + last;
            FT_Vector swap;


            while ( p < q )
            {
                swap = *p;
                *p = *q;
                *q = swap;
                p++;
                q--;
            }
        }

        /* reverse tags table */
        {
            char *p = outline->tags + first;
            char *q = outline->tags + last;
            char swap;


            while ( p < q )
            {
                swap = *p;
                *p = *q;
                *q = swap;
                p++;
                q--;
            }
        }

        first = last + 1;
    }

    outline->flags ^= FT_OUTLINE_REVERSE_FILL;
}


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( FT_Error )
FT_Outline_Render( FT_Library library,
                   FT_Outline *outline,
                   FT_Raster_Params *params )
{
    FT_Error error;
    FT_Bool update = FALSE;
    FT_Renderer renderer;
    FT_ListNode node;


    if ( !library )
    {
        return FT_Err_Invalid_Library_Handle;
    }

    if ( !outline || !params )
    {
        return FT_Err_Invalid_Argument;
    }

    renderer = library->cur_renderer;
    node = library->renderers.head;

    params->source = ( void * ) outline;

    error = FT_Err_Cannot_Render_Glyph;
    while ( renderer )
    {
        error = renderer->raster_render( renderer->raster, params );
        if ( !error || FT_ERROR_BASE( error ) != FT_Err_Cannot_Render_Glyph )
        {
            break;
        }

        /* FT_Err_Cannot_Render_Glyph is returned if the render mode   */
        /* is unsupported by the current renderer for this glyph image */
        /* format                                                      */

        /* now, look for another renderer that supports the same */
        /* format                                                */
        renderer = FT_Lookup_Renderer( library, FT_GLYPH_FORMAT_OUTLINE,
                                       &node );
        update = TRUE;
    }

    /* if we changed the current renderer for the glyph image format */
    /* we need to select it as the next current one                  */
    if ( !error && update && renderer )
    {
        FT_Set_Renderer( library, renderer, 0, 0 );
    }

    return error;
}


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( FT_Error )
FT_Outline_Get_Bitmap( FT_Library library,
                       FT_Outline *outline,
                       const FT_Bitmap *abitmap )
{
    FT_Raster_Params params;


    if ( !abitmap )
    {
        return FT_Err_Invalid_Argument;
    }

    /* other checks are delayed to FT_Outline_Render() */

    params.target = abitmap;
    params.flags = 0;

    if ( abitmap->pixel_mode == FT_PIXEL_MODE_GRAY ||
         abitmap->pixel_mode == FT_PIXEL_MODE_LCD ||
         abitmap->pixel_mode == FT_PIXEL_MODE_LCD_V )
    {
        params.flags |= FT_RASTER_FLAG_AA;
    }

    return FT_Outline_Render( library, outline, &params );
}


/* documentation is in freetype.h */

FT_EXPORT_DEF( void )
FT_Vector_Transform( FT_Vector *vector,
                     const FT_Matrix *matrix )
{
    FT_Pos xz, yz;


    if ( !vector || !matrix )
    {
        return;
    }

    xz = FT_MulFix( vector->x, matrix->xx ) +
         FT_MulFix( vector->y, matrix->xy );

    yz = FT_MulFix( vector->x, matrix->yx ) +
         FT_MulFix( vector->y, matrix->yy );

    vector->x = xz;
    vector->y = yz;
}


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( void )
FT_Outline_Transform( const FT_Outline *outline,
                      const FT_Matrix *matrix )
{
    FT_Vector *vec;
    FT_Vector *limit;


    if ( !outline || !matrix )
    {
        return;
    }

    vec = outline->points;
    limit = vec + outline->n_points;

    for ( ; vec < limit; vec++ )
    {
        FT_Vector_Transform( vec, matrix );
    }
}


#if 0

#define FT_OUTLINE_GET_CONTOUR( outline, c, first, last )  \
  do {                                                     \
    (first) = ( c > 0 ) ? (outline)->points +              \
                            (outline)->contours[c - 1] + 1 \
                        : (outline)->points;               \
    (last) = (outline)->points + (outline)->contours[c];   \
  } while ( 0 )


/* Is a point in some contour?                     */
/*                                                 */
/* We treat every point of the contour as if it    */
/* it were ON.  That is, we allow false positives, */
/* but disallow false negatives.  (XXX really?)    */
static FT_Bool
ft_contour_has( FT_Outline*  outline,
                FT_Short     c,
                FT_Vector*   point )
{
  FT_Vector*  first;
  FT_Vector*  last;
  FT_Vector*  a;
  FT_Vector*  b;
  FT_UInt     n = 0;


  FT_OUTLINE_GET_CONTOUR( outline, c, first, last );

  for ( a = first; a <= last; a++ )
  {
    FT_Pos  x;
    FT_Int  intersect;


    b = ( a == last ) ? first : a + 1;

    intersect = ( a->y - point->y ) ^ ( b->y - point->y );

    /* a and b are on the same side */
    if ( intersect >= 0 )
    {
      if ( intersect == 0 && a->y == point->y )
      {
        if ( ( a->x <= point->x && b->x >= point->x ) ||
             ( a->x >= point->x && b->x <= point->x ) )
          return 1;
      }

      continue;
    }

    x = a->x + ( b->x - a->x ) * (point->y - a->y ) / ( b->y - a->y );

    if ( x < point->x )
      n++;
    else if ( x == point->x )
      return 1;
  }

  return n & 1;
}


static FT_Bool
ft_contour_enclosed( FT_Outline*  outline,
                     FT_UShort    c )
{
  FT_Vector*  first;
  FT_Vector*  last;
  FT_Short    i;


  FT_OUTLINE_GET_CONTOUR( outline, c, first, last );

  for ( i = 0; i < outline->n_contours; i++ )
  {
    if ( i != c && ft_contour_has( outline, i, first ) )
    {
      FT_Vector*  pt;


      for ( pt = first + 1; pt <= last; pt++ )
        if ( !ft_contour_has( outline, i, pt ) )
          return 0;

      return 1;
    }
  }

  return 0;
}


/* This version differs from the public one in that each */
/* part (contour not enclosed in another contour) of the */
/* outline is checked for orientation.  This is          */
/* necessary for some buggy CJK fonts.                   */
static FT_Orientation
ft_outline_get_orientation( FT_Outline*  outline )
{
  FT_Short        i;
  FT_Vector*      first;
  FT_Vector*      last;
  FT_Orientation  orient = FT_ORIENTATION_NONE;


  first = outline->points;
  for ( i = 0; i < outline->n_contours; i++, first = last + 1 )
  {
    FT_Vector*  point;
    FT_Vector*  xmin_point;
    FT_Pos      xmin;


    last = outline->points + outline->contours[i];

    /* skip degenerate contours */
    if ( last < first + 2 )
      continue;

    if ( ft_contour_enclosed( outline, i ) )
      continue;

    xmin       = first->x;
    xmin_point = first;

    for ( point = first + 1; point <= last; point++ )
    {
      if ( point->x < xmin )
      {
        xmin       = point->x;
        xmin_point = point;
      }
    }

    /* check the orientation of the contour */
    {
      FT_Vector*      prev;
      FT_Vector*      next;
      FT_Orientation  o;


      prev = ( xmin_point == first ) ? last : xmin_point - 1;
      next = ( xmin_point == last ) ? first : xmin_point + 1;

      if ( FT_Atan2( prev->x - xmin_point->x, prev->y - xmin_point->y ) >
           FT_Atan2( next->x - xmin_point->x, next->y - xmin_point->y ) )
        o = FT_ORIENTATION_POSTSCRIPT;
      else
        o = FT_ORIENTATION_TRUETYPE;

      if ( orient == FT_ORIENTATION_NONE )
        orient = o;
      else if ( orient != o )
        return FT_ORIENTATION_NONE;
    }
  }

  return orient;
}

#endif /* 0 */


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( FT_Error )
FT_Outline_Embolden( FT_Outline *outline,
                     FT_Pos strength )
{
    return FT_Outline_EmboldenXY( outline, strength, strength );
}


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( FT_Error )
FT_Outline_EmboldenXY( FT_Outline *outline,
                       FT_Pos xstrength,
                       FT_Pos ystrength )
{
    FT_Vector *points;
    FT_Vector v_prev, v_first, v_next, v_cur;
    FT_Int c, n, first;
    FT_Int orientation;


    if ( !outline )
    {
        return FT_Err_Invalid_Argument;
    }

    xstrength /= 2;
    ystrength /= 2;
    if ( xstrength == 0 && ystrength == 0 )
    {
        return FT_Err_Ok;
    }

    orientation = FT_Outline_Get_Orientation( outline );
    if ( orientation == FT_ORIENTATION_NONE )
    {
        if ( outline->n_contours )
        {
            return FT_Err_Invalid_Argument;
        }
        else
        {
            return FT_Err_Ok;
        }
    }

    points = outline->points;

    first = 0;
    for ( c = 0; c < outline->n_contours; c++ )
    {
        FT_Vector in, out, shift;
        FT_Fixed l_in, l_out, d;
        int last = outline->contours[ c ];


        v_first = points[ first ];
        v_prev = points[ last ];
        v_cur = v_first;

        /* compute the incoming vector and its length */
        in.x = v_cur.x - v_prev.x;
        in.y = v_cur.y - v_prev.y;
        l_in = FT_Vector_Length( &in );

        for ( n = first; n <= last; n++ )
        {
            if ( n < last )
            {
                v_next = points[ n + 1 ];
            }
            else
            {
                v_next = v_first;
            }

            /* compute the outgoing vector and its length */
            out.x = v_next.x - v_cur.x;
            out.y = v_next.y - v_cur.y;
            l_out = FT_Vector_Length( &out );

            d = l_in * l_out + in.x * out.x + in.y * out.y;

            /* shift only if turn is less then ~160 degrees */
            if ( 16 * d > l_in * l_out )
            {
                /* shift components are rotated */
                shift.x = FT_DivFix( l_out * in.y + l_in * out.y, d );
                shift.y = FT_DivFix( l_out * in.x + l_in * out.x, d );

                if ( orientation == FT_ORIENTATION_TRUETYPE )
                {
                    shift.x = -shift.x;
                }
                else
                {
                    shift.y = -shift.y;
                }

                shift.x = FT_MulFix( xstrength, shift.x );
                shift.y = FT_MulFix( ystrength, shift.y );
            }
            else
            {
                shift.x = shift.y = 0;
            }

            outline->points[ n ].x = v_cur.x + xstrength + shift.x;
            outline->points[ n ].y = v_cur.y + ystrength + shift.y;

            in = out;
            l_in = l_out;
            v_cur = v_next;
        }

        first = last + 1;
    }

    return FT_Err_Ok;
}


/* documentation is in ftoutln.h */

FT_EXPORT_DEF( FT_Orientation )
FT_Outline_Get_Orientation( FT_Outline *outline )
{
    FT_Vector *points;
    FT_Vector v_prev, v_cur;
    FT_Int c, n, first;
    FT_Pos area = 0;


    if ( !outline || outline->n_points <= 0 )
    {
        return FT_ORIENTATION_TRUETYPE;
    }

    /* We use the nonzero winding rule to find the orientation.       */
    /* Since glyph outlines behave much more `regular' than arbitrary */
    /* cubic or quadratic curves, this test deals with the polygon    */
    /* only which is spanned up by the control points.                */

    points = outline->points;

    first = 0;
    for ( c = 0; c < outline->n_contours; c++ )
    {
        FT_Int last = outline->contours[ c ];


        v_prev = points[ last ];

        for ( n = first; n <= last; n++ )
        {
            v_cur = points[ n ];
            area += ( v_cur.y - v_prev.y ) * ( v_cur.x + v_prev.x );
            v_prev = v_cur;
        }

        first = last + 1;
    }

    if ( area > 0 )
    {
        return FT_ORIENTATION_POSTSCRIPT;
    }
    else if ( area < 0 )
    {
        return FT_ORIENTATION_TRUETYPE;
    }
    else
    {
        return FT_ORIENTATION_NONE;
    }
}


/* END */
